package id.ac.itb.GenericSolver;

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Solver for finding solution using BFS, IDS, DLS, and DFS.
 * @author Edward Samuel
 */
public class Solver {

	public static int nStatus = 0;

	/**
	 * Find a solution (if present) using Breadth-First-Search Algorithm
	 * 
	 * @param state
	 *            Problem state
	 * @return state
	 */
	public static AbstractState BFS(AbstractState state) {
		Queue<AbstractState> queue = new LinkedList<>();
		List<AbstractState> visitedlist = new ArrayList<AbstractState>();

		queue.add(state);
		visitedlist.add(state);

		boolean finish = false;
		while (!queue.isEmpty() && !finish) {
			AbstractState current = queue.poll();
			Collection<AbstractStep> steps = current.getAllPossibleSteps();

			for (AbstractStep step : steps) {
				AbstractState newState = current.createAppliedState(step);

				if (newState.isSolution()) {
					nStatus++;
					finish = true;
					current.addChild(step, newState);
					newState.setPath(true);
					break;
				} else {
					if (!visitedlist.contains(newState)) {
						nStatus++;
						current.addChild(step, newState);
						queue.add(newState);
						visitedlist.add(newState);
					}
				}
			}
		}
		return state;
	}

	/**
	 * Find a solution (if present) using Iterative-Deepening-Search Algorithm
	 * 
	 * @param state
	 *            Problem state
	 * @return state
	 */
	public static AbstractState IDS(AbstractState state) {
		for (int depth = 0;; depth++) {
			DLS(state, depth);
			if (state.isPath()) {
				break;
			}
		}
		return state;
	}

	/**
	 * Find a solution (if present) using Depth-Limited-Search (Rekursive)
	 * Algorithm
	 * 
	 * @param state
	 *            Problem state
	 * @param depth
	 *            The depth for finding solution
	 * @param visitedlist
	 *            Visited state
	 * @return state
	 */
	public static AbstractState DLS(AbstractState state, int depth) {
		nStatus++;
		if (state.isSolution()) {
			state.setPath(true);
		} else if (depth > 0) {
			Collection<AbstractStep> steps = state.getAllPossibleSteps();
			for (AbstractStep step : steps) {
				AbstractState newState = state.createAppliedState(step);
				state.addChild(step, newState);
				newState = DLS(newState, depth - 1);
				if (newState.isPath()) {
					break;
				}
			}
		}
		return state;
	}

	/**
	 * Find a solution (if present) using Depth-First-Search (Rekursive)
	 * Algorithm
	 * 
	 * @param state
	 *            Problem state
	 * @param visitedlist
	 *            Visited state
	 * @return state
	 */
	public static AbstractState DFS(AbstractState state,
			List<AbstractState> list) {
		nStatus++;
		if (state.isSolution()) {
			state.setPath(true);
		} else {
			Collection<AbstractStep> steps = state.getAllPossibleSteps();
			for (AbstractStep step : steps) {
				AbstractState newState = state.createAppliedState(step);
				if (!list.contains(newState)) {
					state.addChild(step, newState);
					list.add(newState);
					newState = DFS(newState, list);
					if (newState.isPath()) {
						break;
					}
				}
			}
		}
		return state;
	}
}
